#ifndef SPW_LIST_H
#define SPW_LIST_H
#include <spw_config.h>
#include <memory/spw_alloc.h>
#include <iterator/spw_iterator.h>
#include <utility/spw_move_in.h>
#include <type_traits>
#include <initializer_list>

using namespace spwconfig;
namespace spwstd{
/*ListNode*/
// ListNodeBase
struct ListNodeBase_in 
{
    ListNodeBase_in* next_;
    ListNodeBase_in* prev_;

    // 将该节点插入到pos节点前
    void Hook_in(ListNodeBase_in* const pos);
    // 将该节点从链表中去除
    void Unhook_in();

    static void Swap(ListNodeBase_in& x, ListNodeBase_in& y);
};

// ListNodeHeader
struct ListNodeHeader_in: public ListNodeBase_in
{
    size_t size_;

    ListNodeHeader_in() {
        Init();
    }

    ListNodeHeader_in(ListNodeHeader_in&& x)
        : ListNodeBase_in{x.next_, x.prev_}, size_(x.size_)
    {
        if (x.Base()->next_ == x.Base())
            this->next_ = this->prev_ = this;
        else {
            this->next_->prev_ = this->prev_->next_ = this->Base();
            x.Init();
        }
    }

    void Init() {
        this->next_ = this->prev_ = this;
        this->size_ = 0;
    }

    void MoveNodes(ListNodeHeader_in&& x)
    {
       ListNodeBase_in* const xnode = x.Base();
       if (xnode->next_ == xnode)
           Init();
       else {
           ListNodeBase_in* const node = this->Base();
           node->next_ = xnode->next_;
           node->prev_ = xnode->prev_;
           node->next_->prev_ = node->prev_->next_ = node;
           size_ = x.size_;
           x.Init();
       }
    }

private:
    ListNodeBase_in* Base() { return this; }
};

// ListNode
template<typename Tp>
struct ListNode_in: public ListNodeBase_in
{
    Tp data_;

    Tp* Getptr() 
    {
        return spwuti::addressOf(data_);
    }
    const Tp* Getptr() const 
    {
        return spwuti::addressOf(data_);
    }
};

/*ListIterator*/
template<typename Tp>
struct ListIterator_in
{
    using Self = ListIterator_in<Tp>;
    using Node = ListNode_in<Tp>;
    using DifferType = spwconfig::ptrdiff_t;
    using IteratorCategory = spwstd::BidirectionalIterTag;
    using ValueType = Tp;
    using Pointer = Tp*;
    using Refer = Tp&;

    ListIterator_in(): node_() { }
    explicit ListIterator_in(ListNodeBase_in* x): node_(x) { }

    Self ConstCast() const 
    { return *this; }

    Refer operator*() const 
    { return *static_cast<Node*>(node_)->Getptr(); }

    Pointer operator->() const 
    { return static_cast<Node*>(node_)->Getptr(); }

    Self& operator++() 
    {
        node_ = node_->next_;
        return *this;
    }

    Self operator++(int) 
    {
        Self tmp = *this;
        node_ = node_->next_;
        return tmp;
    }

    Self& operator--() 
    {
        node_ = node_->prev_;
        return *this;
    }

    Self operator--(int) 
    {
        Self tmp = *this;
        node_ = node_->prev_;
        return tmp;
    }

    friend bool operator==(const Self& x, const Self& y)
    { return x.node_ == y.node_; }

    friend bool operator!=(const Self& x, const Self& y)
    { return x.node_ != y.node_; }

    ListNodeBase_in* node_;
};

template<typename Tp>
struct ListConstIterator_in
{
    using Self = ListConstIterator_in<Tp>;
    using Node = const ListNode_in<Tp>;
    using Iterator = ListIterator_in<Tp>;
    using DifferType = spwconfig::ptrdiff_t;
    using IteratorCategory = spwstd::BidirectionalIterTag;
    using ValueType = Tp;
    using Pointer = const Tp*;
    using Refer = const Tp&;

    ListConstIterator_in(): node_() { }
    explicit ListConstIterator_in(const ListNodeBase_in* x): node_(x) { }
    ListConstIterator_in(const Iterator& x): node_(x.node_) { }

    Iterator ConstCast() const 
    {
        return Iterator(const_cast<ListNodeBase_in*>(node_));
    }

    Refer operator*() const
    { return *static_cast<Node*>(node_)->Getptr(); }

    Pointer operator->() const 
    { return static_cast<Node*>(node_)->Getptr(); }

    Self& operator++() 
    {
        node_ = node_->next_;
        return *this;
    }

    Self operator++(int) 
    {
        Self tmp = *this;
        node_ = node_->next_;
        return tmp;
    }

    Self& operator--() 
    {
        node_ = node_->prev_;
        return *this;
    }

    Self operator--(int) 
    {
        Self tmp = *this;
        node_ = node_->prev_;
        return tmp;
    }

    friend bool operator==(const Self& x, const Self& y)
    { return x.node_ == y.node_; }

    friend bool operator!=(const Self& x, const Self& y)
    { return x.node_ != y.node_; }

    const ListNodeBase_in* node_;
};

/*List*/
// ListBase
template<typename Tp, typename Alloc>
class ListBase_in
{
protected:
    using NodeAllocType = typename spwdetail::AllocRebind<Alloc,ListNode_in<Tp>>;

    struct ListImpl_in: public NodeAllocType
    {
        ListNodeHeader_in h_node_;

        ListImpl_in():NodeAllocType(){ }
        ListImpl_in(ListImpl_in&&) = default;
        ListImpl_in(const NodeAllocType& a): NodeAllocType(a){ }
    };

    ListImpl_in impl_;

    spwconfig::size_t GetSize() const { return impl_.h_node_.size_; }
    void SetSize(spwconfig::size_t n) { impl_.h_node_.size_ = n; }
    void IncSize(spwconfig::size_t n) { impl_.h_node_.size_ += n; }
    void DecSize(spwconfig::size_t n) { impl_.h_node_.size_ -= n; }

    typename NodeAllocType::Pointer 
    GetNode()
    {
        return spwstd::AllocInterface<ListNode_in<Tp>, NodeAllocType>::s_allocate();
    }

    void PutNode(typename NodeAllocType::Pointer p)
    {
        spwstd::AllocInterface<ListNode_in<Tp>, NodeAllocType>::s_deallocate(p);
    }

public:
    NodeAllocType& GetNodeAllocator() { return impl_; }
    const NodeAllocType& GetNodeAllocator() const { return impl_; }

    ListBase_in() = default;
    ListBase_in(ListBase_in&&) = default;
    ListBase_in(const NodeAllocType& a)
        : impl_(a) {}

    ~ListBase_in()
    { Clear(); }

    void Init()
    { this->impl_.h_node_.Init(); }

    void Clear();
};

// List
template<typename Tp, typename Alloc=spwstd::DefaultAlloc<Tp>>
class List: protected ListBase_in<Tp, Alloc>
{
    static_assert(std::is_same_v<typename std::remove_cv<Tp>::type, Tp>, 
                  "valuetype must non-const non-volatile");
    using Base = ListBase_in<Tp, Alloc>;

public:
    using ValueType = Tp;
    using Pointer = Tp*;
    using ConstPointer = const Tp*;
    using Refer = Tp&;
    using ConstRefer = const Tp&;
    using Iter = ListIterator_in<Tp>;
    using ConstIter = ListConstIterator_in<Tp>;
    using SizeType = spwconfig::size_t;
    using DifferType = spwconfig::ptrdiff_t;
    using AllocT = Alloc;
    using NodeAllocT = typename Base::NodeAllocType; // 生成Node的alloc

protected:
    using Node = ListNode_in<Tp>;
    using Base::impl_;

    template<typename Integer>
    void InitDispatchInteger_in(Integer n, Integer x)
    { FillInit_in(static_cast<SizeType>(n), x); }

    template<typename InputIter>
    void InitDispatchInputIter_in(InputIter first, InputIter last)
    {
        for (; first != last; ++first)
        {
            PushBack(*first);
        }
    }

    template<typename... Args>
    Node* CreateNode_in(Args&&... args)
    {
        auto p = this->GetNode();
        // TODO：s_construct可能构造不成功，
        spwstd::AllocInterface<
            typename spwstd::AllocTraits<NodeAllocT>::ValueType, NodeAllocT>
                ::s_construct(p->Getptr(), spwuti::forward<Args>(args)...);
        return p;
    }

    template<typename... Args>
    void Insert_in(Iter pos, Args&&... args)
    {
        Node* tmp = CreateNode_in(spwuti::forward<Args>(args)...);
        tmp->Hook_in(pos.node_);
        this->IncSize(1);
    }

    void Erase_in(Iter pos) {
        this->DecSize(1);
        pos.node_->Unhook_in();
        Node* n = static_cast<Node*>(pos.node_);
        spwstd::AllocInterface<typename spwstd::AllocTraits<NodeAllocT>::ValueType, NodeAllocT>
            ::s_destroy(n);
        this->PutNode(n);
    }

    void FillInit_in(SizeType n, const ValueType& x)
    {
        for(; n; --n) {
            this->Insert_in(this->End(), x);
        }
    }

    spwconfig::size_t NodeCount_in() const
    {
        return this->GetSize();
    }

    template<typename InputIter>
    void AssignDispatch_in(InputIter first, InputIter last);

    Iter Getpos_in(SizeType& num);

public:
    List() = default;

    explicit List(SizeType n, const ValueType& value = ValueType{})
        : Base{}
    {
        FillInit_in(n, value);
    }

    List(const List& x)
        : Base{x.GetNodeAllocator()}
    { this->InitDispatchInputIter_in(x.Begin(), x.End()); }

    List(List&&) = default;

    List(std::initializer_list<ValueType> l)
        : Base{NodeAllocT{}}
    { this->InitDispatchInputIter_in(l.begin(), l.end()); }

    template<typename InputIter, typename = spwdetail::RequireInputIter<InputIter>>
    List(InputIter first, InputIter last)
        : Base{}
    { InitDispatchInputIter_in(first, last); }

    ~List() = default;

    List& operator=(const List& x);
    List& operator=(List&& x)
    {
        this->Clear();
        this->Swap(x);
        return *this;
    }

    List& operator=(std::initializer_list<ValueType> l)
    {
        List tmp(l.begin(), l.end());
        this->Swap(tmp);
        return *this;
    }

    /* 元素访问 */
    Refer Front() 
    { return *Begin(); }

    ConstRefer Front() const
    { return *Begin(); }

    Refer Back() 
    {
        Iter tmp = End();
        --tmp;
        return *tmp;
    }

    ConstRefer Back() const
    {
        ConstIter tmp = End();
        --tmp;
        return *tmp;
    }

    /* 迭代 */
    Iter Begin()
    {
        return Iter{this->impl_.h_node_.next_};
    }

    ConstIter Begin() const
    {
        return ConstIter{this->impl_.h_node_.next_};
    }

    Iter End() 
    {
        return Iter{&this->impl_.h_node_};
    }

    ConstIter End() const
    {
        return ConstIter(&this->impl_.h_node_);
    }

    ConstIter Cbegin() const
    {
        return ConstIter{this->impl_.h_node_.next_};
    }

    ConstIter Cend() const
    {
        return ConstIter(&this->impl_.h_node_);
    }

    /* 修改*/
    void PushBack(const ValueType& x)
    {
        this->Insert_in(End(), x);
    }

    void PushBack(ValueType&& x)
    {
        this->Insert_in(End(), spwuti::move(x));
    }

    void PopBack() {
        this->Erase_in(Iter(this->impl_.h_node_.prev_));
    }

    void PushFront(const ValueType& x) {
        this->Insert_in(Begin(), x);
    }

    void PopFront() {
        this->Erase_in(Begin());
    }

    void Clear()
    { 
        Base::Clear(); 
        Base::Init();
    }

    void Swap(List& x)
    {
        ListNodeBase_in::Swap(this->impl_.h_node_, x.impl_.h_node_);
        auto xsize = x.GetSize();
        x.SetSize(this->GetSize());
        this->SetSize(xsize);
    }

    Iter Insert(ConstIter pos, const ValueType& value);
    Iter Insert(ConstIter pos, ValueType&& value);

    template<typename... Args>
    Iter Emplace(ConstIter pos, Args&&... args);

    Iter Erase(ConstIter pos);

    void Resize(SizeType newsize, const ValueType& value=ValueType{});

    /* 容量 */
    bool Empty() const 
    {
        return this->impl_.h_node_.next_ == &this->impl_.h_node_;
    }

    SizeType Size() const 
    {
        return NodeCount_in();
    }

    /*TODO: 操作merge, splice, unique, sort */
};

/* ListNodeBase func */
void ListNodeBase_in::Hook_in(ListNodeBase_in* const pos)
{
    this->next_ = pos;
    this->prev_ = pos->prev_;
    pos->prev_->next_ = this;
    pos->prev_ = this;
}

void ListNodeBase_in::Unhook_in()
{
    ListNodeBase_in* const next = this->next_;
    ListNodeBase_in* const prev = this->prev_;
    prev->next_ = next;
    next->prev_ = prev;
}

void ListNodeBase_in::Swap(ListNodeBase_in& x, ListNodeBase_in& y)
{
    if (x.next_ != &x) {
        if (y.next_ != &y) {
            spwuti::swap(x.next_, y.next_);
            spwuti::swap(x.prev_, y.prev_);
            x.next_->prev_ = x.prev_->next_ = &x;
            y.next_->prev_ = y.prev_->next_ = &y;
        } else {
            y.next_ = x.next_;
            y.prev_ = x.prev_;
            y.next_->prev_ = y.prev_->next_ = &y;
            x.next_ = x.prev_ = &x;
        }
    } else if(y.next_ != &y) {
        x.next_ = y.next_;
        x.prev_ = y.prev_;
        x.next_->prev_ = x.prev_->next_ = &x;
        y.next_ = y.prev_ = &y;
    }
}

/* ListBase func */
template<typename Tp, typename Alloc>
void ListBase_in<Tp, Alloc>::Clear()
{
    using Node = ListNode_in<Tp>;
    ListNodeBase_in* cur = impl_.h_node_.next_;
    while (cur != &impl_.h_node_)
    {
        Node* tmp = static_cast<Node*>(cur);
        cur = tmp->next_;
        AllocInterface<typename AllocTraits<NodeAllocType>::ValueType, NodeAllocType>::s_destroy(tmp);
        PutNode(tmp);
    }
}

/* List func */
template<typename Tp, typename Alloc>
List<Tp, Alloc>&
List<Tp, Alloc>::operator=(const List& x)
{
    if (this != spwuti::addressOf(x)) {
        AssignDispatch_in(x.Begin(), x.End());
    }
    return *this;
}

template<typename Tp, typename Alloc>
template<typename InputIter>
void List<Tp, Alloc>::AssignDispatch_in(InputIter first, InputIter last)
{
    auto len = distance(last - first);
    List tmp(first, last);
    this->Swap(tmp);
}

template<typename Tp, typename Alloc>
template<typename... Args>
typename List<Tp, Alloc>::Iter 
List<Tp, Alloc>::Emplace(ConstIter pos, Args&&... args) {
    Node* tmp = CreateNode_in(spwuti::forward<Args>(args)...);
    tmp->Hook_in(pos.ConstCast().node_);
    this->IncSize(1);
    return Iter(tmp);
}

template<typename Tp, typename Alloc>
typename List<Tp, Alloc>::Iter 
List<Tp, Alloc>::Insert(ConstIter pos, const ValueType& value) {
    Node* tmp = CreateNode_in(value);
    tmp->Hook_in(pos.ConstCast().node_);
    this->IncSize(1);
    return Iter(tmp);
}

template<typename Tp, typename Alloc>
typename List<Tp, Alloc>::Iter 
List<Tp, Alloc>::Insert(ConstIter pos, ValueType&& value) {
    return Emplace(pos, spwuti::move(value));
}

template<typename Tp, typename Alloc>
typename List<Tp, Alloc>::Iter 
List<Tp, Alloc>::Erase(ConstIter pos) {
    Iter ret = Iter(pos.node_->next_);
    Erase_in(pos.ConstCast());
    return ret;
}

template<typename Tp, typename Alloc>
typename List<Tp, Alloc>::Iter 
List<Tp, Alloc>::Getpos_in(SizeType& num) {
    Iter i;
    const SizeType len = Size();
    if (num < len) {
        i = Begin();
        spwstd::advance(i, num);
        num = 0;
        return i;
    } else {
        i = End();
    }
    num -= len;
    return i;
}

template<typename Tp, typename Alloc>
void List<Tp, Alloc>::Resize(SizeType newsize, const ValueType& value) {
    Iter pos = Getpos_in(newsize);
    if (newsize) {
        while(newsize--)
            Insert(End(), value);
    }
    else {
        DifferType len = spwstd::distance(pos, End());
        while(len--) {
            PopBack();
        }
    }
}
}// namespace spwstd

#endif // SPW_LIST_H

